/* ************************************************************************
> File Name:     6.c
> Author:        zhfu
> mail:          3346897597@qq.com
> Created Time:  2022年04月19日 星期二 10时15分16秒
> Description:   
 ************************************************************************/
#include<stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
#define LEN 3 

struct pointer {
    int row, col;
};

struct pointer queue[LEN];
int d = -1;  /*用来指示head和tail的相对位置，因为这里的实现是循环队列，当队列为空和满时都是head==tail，d为-1时head==tail为空，d=1时head=tail为满*/
int head = 0, tail = 0;

void enqueue(struct pointer p)
{
    queue[tail++] = p;

    if (tail == LEN){
        tail = 0;
        d *= -1;
    }
}

struct pointer dequeue()
{
    struct pointer p = queue[head];
    ++head;

    if (head == LEN){
        head = 0;
        d *= -1;
    }
    return p;
}

int is_empty()
{
    return head == tail && d == -1;
}

int is_full()
{
    return head == tail && d == 1;
}

int maze[MAX_ROW][MAX_COL] = {
	0, 1, 0, 0, 0,
	0, 1, 0, 1, 0,
	0, 0, 0, 0, 0,
	0, 1, 1, 1, 0,
	0, 0, 0, 1, 0,
};

int cnt = 0;/*为了更直观表现每次print_maze，用来标号*/

void print_maze(void)
{
    int i, j;
    printf("-------%d----------\n", cnt++);
    for (i = 0; i < MAX_ROW; ++i){
        for (j = 0; j < MAX_COL; ++j){
            printf("%d ", maze[i][j]);
        }
        putchar('\n');
    }
    printf("*****************\n");
}

void visit(int row, int col)
{
    struct pointer visit_pointer = {row, col};
    maze[row][col] = 2;
    if (is_full()){
       printf("Full!");
    }
    enqueue(visit_pointer);
}

int main()
{
    struct pointer p = {0, 0}; /*起点*/
    maze[0][0] = 2;
    enqueue(p);

    while (!is_empty()){
        p = dequeue();

        if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
            break;
        if (p. row + 1 < MAX_ROW && maze[p.row + 1][p.col] == 0)
            visit(p.row + 1, p.col);
        if (p.col + 1 < MAX_COL && maze[p.row][p.col + 1] == 0)
            visit(p.row, p.col + 1);
        if (p.row - 1 >= 0 && maze[p.row - 1][p.col] == 0)
            visit(p.row - 1, p.col);
        if (p.col - 1 >= 0 && maze[p.row][p.col - 1] == 0)
            visit(p.row, p.col - 1);
        print_maze();
    }

    if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
        printf("Yes!\n");
    else
        printf("No!\n");

    return 0;
}
